#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

vector<vector<int>> threesum(vector<int>& nums){
    //先将数组进行排序
    sort(nums.begin(), nums.end());
    //定义一个二维数组用来存放组合数组
    vector<vector<int>> vv;

    //定义三个指针
    int i = 0;
    int left = i + 1;
    int right = nums.size() - 1;

    int target = 0 - nums[i];

    //i指针指向的是小于等于零的元素，这样可以保证三数之和为0
    while(nums[i]<=0&&left<right){
        if(nums[left]+nums[right]>target){
            right--;
        }
        else if(nums[left]+nums[right]<target){
            left++;
        }
        else{
            vv.push_back({nums[i],nums[left++],nums[right--]});
            
            //左右指针遇到相等元素时，跳过去重
            //处理边界情况，左指针要保证在右指针的左边，右指针要保证在左指针的右边
            while(left<right&&nums[left]==nums[left-1]){
                left++;
            }
            while(right>left&&nums[right]==nums[right+1]){
                right--;
            }
        }

        //当出现左右指针相等或者互换方向时，重新设置i指针的值，同时i指针也要去重
        //处理边界情况，i可能会越界
        if(left>=right){
            i++;
            while(i+1<nums.size()&&nums[i-1]==nums[i]){
                i++;
            }
            left=i+1;
            right = nums.size() - 1;
            target = 0 - nums[i];
        }
    }

    return vv;
}

int main(){
    vector<int> v={-1,0,1,2,-1,-4};
    vector<vector<int>> vv = threesum(v);

    for(auto v : vv){
        for(auto e : v){
            cout << e << " ";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}